package leetcode.other.dynamic_programming;

import java.util.Arrays;

/**
 * @Description: https://leetcode.cn/problems/coin-change/
 *
 * 假设有 25 分、10 分、5 分和 1 分的硬币，现在要找给客户 41 分的零钱，如何办到硬币个数最少？
 * 贪心策略：优先选择面值最大的硬币
 * ① 选择面值最大的硬币 25，然后用 41 - 25 = 16
 * ② 选择面值最大的硬币 10，然后用 16 - 10 = 6
 * ③ 选择面值最大的硬币 5，然后用 6 - 5 = 1
 * ④ 选择面值最大的硬币 1，然后用 1 - 1 = 0
 * 最终的结果是 4 个硬币
 * 25分、20分、5分、1分的硬币各一枚
 * @Author Ammar
 * @Create 2023/7/2 22:08
 */
public class _322_零钱兑换 {

    public static void main(String[] args) {
        Integer[] faces = {25, 20, 5, 1};
        // 实际上本题最优解：2 枚 20 分，1 枚 1 分，只需要3枚
//        System.out.println(coinChange02(40, new int[]{5 , 20 ,25}));
        System.out.println(coinChange01(41));
    }

    /**
     * 通用
     * @param faces
     * @param n
     * @return
     */
    static int coinChange02(int n, int[] faces) {
        if (n < 1 || faces == null || faces.length == 0) return -1;
        int[] dp = new int[n + 1]; // 存放 coinChange(i) 的结果 i 从 1到n
        for (int i = 1; i <= n; i++) {
            int min = Integer.MAX_VALUE;
            for (int face : faces) {
                if (i < face) continue;
                if (dp[i - face] < min && dp[i - face] != -1) {
                    min = dp[i - face];
                }
            }
            if (min == Integer.MAX_VALUE) {
                dp[i] = -1;
            } else {
                dp[i] = min + 1;
            }
        }
        return dp[n];
    }

    static int coinChange01(int n) {
        if (n < 1) return -1;
        int[] dp = new int[n + 1];
        int[] faces = new int[dp.length];
        for (int i = 1; i <= n; i++) {
//            int min = Integer.MAX_VALUE;
//            if (i >= 1 && dp[i - 1] < min) {
//                min = dp[i - 1];
//                faces[i] = 1;
//            }
            int min = dp[i - 1];
            faces[i] = 1;
            if (i >= 5 && dp[i - 5] < min) {
                min = dp[i - 5];
                faces[i] = 5;
            }
            if (i >= 20 && dp[i - 20] < min) {
                min = dp[i - 20];
                faces[i] = 20;
            }
            if (i >= 25 && dp[i - 25] < min) {
                min = dp[i - 25];
                faces[i] = 25;
            }
            dp[i] = min + 1;
            print(faces, i);
        }
        return dp[n];
    }

    static void print(int[] faces, int n) {
        System.out.print("[" + n + "] = ");
        while (n > 0) {
            // faces[n] 表示上一次选择的硬币面值
            System.out.print(faces[n] + " ");
            n -= faces[n];
        }
        System.out.println();
    }


    /**
     * 递推
     */
    static int coinChange0(int n) {
        if (n < 1) return -1;
        int[] dp = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            int min = Integer.MAX_VALUE;
            if (i >= 1) min = Math.min(dp[i - 1], min);
            if (i >= 5) min = Math.min(dp[i - 5], min);
            if (i >= 20) min = Math.min(dp[i - 20], min);
            if (i >= 25) min = Math.min(dp[i - 25], min);
            dp[i] = min + 1;
        }
        return dp[n];
    }


    /**
     * 记忆化搜索(自顶向下)
     * @param n
     * @return
     */
    static int coinChange2(int n) {
        if (n < 1) return -1;
        int dp[] = new int[n + 1]; // 存放 coinChange(i) 的结果 i 从 1到n
        int[] faces = {1, 5, 20, 25};
        for (int face : faces) {
            if (n < face) break;
            dp[face] = 1;
        }
        return coinChange2(n, dp);
    }

    static int coinChange2(int n, int[] dp) {
        if (n < 1) return Integer.MAX_VALUE;
        if (dp[n] == 0) {
            int min1 = Math.min(coinChange2(n - 25, dp), coinChange2(n - 20, dp));
            int min2 = Math.min(coinChange2(n - 5, dp), coinChange2(n - 1, dp));
            dp[n] = Math.min(min1, min2) + 1;
        }
        return dp[n];
    }


    /**
     * 暴力递归(自顶向下，有重叠子问题)
     * 重复执行 coinChange(i) i < n
     */
    static int coinChange1(int n) {
        // n < 1 时，为了后续比较，返回一个最大值
        if (n < 1) return Integer.MAX_VALUE;
        if (n == 25 || n == 20 || n == 5 || n == 1) return 1;
        int min1 = Math.min(coinChange1(n - 25), coinChange1(n - 20));
        int min2 = Math.min(coinChange1(n - 5), coinChange1(n - 1));
        return Math.min(min1, min2) + 1;
    }



    static void coinChange_greedy_error(Integer[] faces, int money) {
        // 从大到小排序
        Arrays.sort(faces, (Integer o1, Integer o2) -> o2 - o1);
        int coins = 0;
        for (int i = 0; i < faces.length; i++) {
            while (money >= faces[i]) {
                System.out.println("面值为 " + faces[i] + " 的硬币");
                money -= faces[i];
                coins++;
            }
        }
        System.out.println("硬币个数为 " + coins);
    }
}
